# 给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
#
#  示例 1:
# 输入: s = "abcabcbb"
# 输出: 3
# 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
#
#  示例 2:
# 输入: s = "bbbbb"
# 输出: 1
# 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
#
#  示例 3:
# 输入: s = "pwwkew"
# 输出: 3
# 解释: 因为无重复字符的最长子串是"wke"，所以其长度为 3。
#     请注意，你的答案必须是 子串 的长度，"pwke"是一个子序列，不是子串。
#
#
#  Related Topics 哈希表 字符串 滑动窗口 👍 10111 👎 0
from typing import List
from collections import defaultdict


class Solution:

    def findAnagrams2(self, s: str, p: str) -> List[int]:
        """
        字典优化 window 实现(异位词字典一定是一样的)
        """
        len_s, len_p = len(s), len(p)
        if len_s < len_p:
            return []
        left, right, res, window, char_counts = 0, len_p - 1, [], defaultdict(int), defaultdict(int)
        for i, ch in enumerate(p):
            char_counts[ch] += 1
            window[s[i]] += 1

        # 这个写法等价于下面的写法
        for i in range(len_s - len_p + 1):
            if char_counts == window:
                res.append(i)
            window[s[i]] -= 1
            if window[s[i]] == 0:
                del window[s[i]]
            if i + len_p < len_s:
                window[s[i + len_p]] += 1

        # 这个写法等价于上面的写法
        # while left <= right < len_s:
        #     if (right - left + 1) == len_p:
        #         if char_counts == window:
        #             res.append(left)
        #         right += 1
        #         if right < len_s:
        #             window[s[right]] += 1
        #         window[s[left]] -= 1
        #         if window[s[left]] == 0:
        #             del window[s[left]]
        #         left += 1
        #     elif (right - left + 1) > len_p:
        #         left += 1
        #         window[s[left]] -= 1
        #         if window[s[left]] == 0:
        #             del window[s[left]]
        #     else:
        #         break
        return res

    def findAnagrams1(self, s: str, p: str) -> List[int]:
        """
        暴力法判断
        异位词排序后一定是一样的，滑动后排序，然后判断两个 list 是否一样
        """

        def is_anagram(str1: str, str2: str) -> bool:
            return sorted(str1) == sorted(str2)

        len_s, len_p = len(s), len(p)
        if len_s < len_p:
            return []
        left, right, res = 0, len_p - 1, []
        while left <= right < len_s:
            if (right - left + 1) == len_p:
                if is_anagram(s[left:right + 1], p):
                    res.append(left)
                left += 1
                right += 1
            elif (right - left + 1) < len_p:
                right += 1
            else:
                left += 1
        return res

    def findAnagrams(self, s: str, p: str) -> List[int]:
        return self.findAnagrams2(s, p)


if __name__ == '__main__':
    s, p = "acdcaeccde", "c"
    # s, p = "aaaaaaaaaa", "aaaaaaaaaaaaa"
    print(Solution().findAnagrams1(s, p) == Solution().findAnagrams(s, p))
